1393C - Pinkie Pie Eats Patty-cakes - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
int a[MAXN], n, sz = 0;
vector<int> v;
bool b[MAXN];

bool cmp(int a, int b)  {
    return a > b;
}

bool check(int d) {
    memset(b, false, sizeof(b));
    for (int i = 0; i < sz; i++)    {
        int l = i + 1;

        for (int j = 0; j < v[i]; j++) {
            if (l > n) return false;
            if (b[l]) continue;
            b[l] = true;
            l += d; 
        }
    }

    return true;
}   

void solve()    {
    v.clear();
    sz = 0;
    memset(a, false, sizeof(a));
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[x]++;
    }

    for (int i = 1; i <= n; i++)    {
        if (a[i])   {
            v.push_back(a[i]);
            sz++;
        }
    }

    sort(v.begin(), v.end(), cmp);
    int l = 1, r = n, mid, ans = 1;
    while (l <= r)  {
        mid = ((l + r) >> 1);
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }

    cout << ans - 1 << '\n';
}

int main()  {
    // freopen("CHECK.INP", "r", stdin);
    // freopen("CHECK.OUT", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;

    while (t--)
        solve();

    return 0;
}